package com.pkk.penguin.frame.know.java.interview.year2021.atguigu_20210226.lru;

import java.util.HashMap;
import java.util.Map;

/**
 * lru算法的简单实现方式之二
 *
 * @author peikunkun
 * @version V1.0
 * @date 2021-03-15 09:36
 **/
public class LruImplTwo<K, V> {

  private static final long serialVersionUID = -7880160307482524508L;


  /**
   * node节点
   *
   * @author peikunkun
   * @Param null
   * @return
   * @date 2021/3/15 0015 上午 11:45
   * @since
   */
  static class Node<K, V> {

    private K key;

    private V value;

    /**
     * 前一个
     */
    private Node<K, V> prev;

    /**
     * 后一个
     */
    private Node<K, V> next;


    public Node() {
      this.prev = this.next = null;
    }

    public Node(K key, V value) {
      this.key = key;
      this.value = value;
      this.prev = this.next = null;
    }
  }


  /**
   * 双向链表
   *
   * @author peikunkun<br>
   * @version V1.0<br>
   * @date 2021/3/15 0015 上午 11:45<br>
   * @since <><br>
   */
  static class DoubleLinkedList<K, V> {


    /**
     * 头指针
     */
    private Node<K, V> head;

    /**
     * 尾指针
     */
    private Node<K, V> tail;


    public DoubleLinkedList() {
      //初始化指针
      this.head = new Node<>();
      this.tail = new Node<>();

      //创建连接关系
      this.head.next = tail;
      this.tail.prev = head;
    }


    public void addHead(Node<K, V> node) {
      node.prev = head;
      node.next = head.next;
      head.next.prev = node;
      head.next = node;
    }

    public void removeNode(Node<K, V> node) {
      node.prev.next = node.next;
      node.next.prev = node.prev;

      //help gc
      node.prev = null;
      node.next = null;
    }

    /**
     * 获取最近最少使用的
     *
     * @return void
     * @Param
     * @author peikunkun
     * @date 2021/3/15 0015 下午 5:26
     * @since
     */
    public Node<K, V> getLeastRecentlyUsed() {
      return this.tail.prev;
    }
  }


  private int capacity;
  private Map<K, Node<K, V>> map;
  private DoubleLinkedList<K, V> doubleLinkedList;

  public LruImplTwo(int capacity) {
    this.capacity = capacity;
    map = new HashMap<>();
    doubleLinkedList = new DoubleLinkedList<>();
  }


  /**
   * 获取数据
   *
   * @return V
   * @Param key
   * @author peikunkun
   * @date 2021/3/15 0015 下午 5:58
   * @since
   */
  public V get(K key) {
    if (!map.containsKey(key)) {
      return null;
    }

    final Node<K, V> kvNode = map.get(key);
    doubleLinkedList.removeNode(kvNode);
    doubleLinkedList.addHead(kvNode);
    return kvNode.value;
  }


  /**
   * put操作
   *
   * @return void
   * @Param key
   * @Param value
   * @author peikunkun
   * @date 2021/3/15 0015 下午 5:58
   * @since
   */
  public void put(K key, V value) {
    if (map.containsKey(key)) {
      final Node<K, V> kvNode = map.get(key);
      kvNode.value = value;
      map.put(key, kvNode);

      doubleLinkedList.removeNode(kvNode);
      doubleLinkedList.addHead(kvNode);
    } else {
      //达到最大值-删除最不常用的数据
      if (map.size() == capacity) {
        final Node<K, V> leastRecentlyUsed = doubleLinkedList.getLeastRecentlyUsed();
        map.remove(leastRecentlyUsed.key);
        doubleLinkedList.removeNode(leastRecentlyUsed);
      }
      final Node<K, V> kvNode = new Node<>(key, value);
      map.put(kvNode.key, kvNode);
      doubleLinkedList.addHead(kvNode);
    }
  }


  public static void main(String[] args) {
    LruImplTwo<Integer, Integer> a = new LruImplTwo<>(3);
    a.put(1, 1);
    a.put(2, 2);
    a.put(3, 3);
    a.put(4, 4);
    System.out.println(a.map.keySet());
    a.put(2, 3);
    a.put(5, 5);
    System.out.println(a.map.keySet());
    a.put(6, 6);
    a.put(3, 4);
    System.out.println(a.map.keySet());
    final Integer integer = a.get(5);
    a.put(7, 7);
    System.out.println(a.map.keySet());
  }


}
